package com.cg.leetcode;

import org.junit.Test;

import java.util.Arrays;

/**
 * 354.俄罗斯套娃信封问题
 *
 * @program: LeetCode->LeetCode_354
 * @author: cg
 * @create: 2022-04-17 18:42
 **/
public class LeetCode_354 {

    @Test
    public void test354() {
        System.out.println(maxEnvelopes(new int[][]{{5, 4}, {6, 4}, {6, 7}, {2, 3}}));
    }

    /**
     * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
     * <p>
     * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
     * <p>
     * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
     * <p>
     * 注意：不允许旋转信封。
     * <p>
     * 示例 1：
     * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
     * 输出：3
     * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
     * <p>
     * 示例 2：
     * 输入：envelopes = [[1,1],[1,1],[1,1]]
     * 输出：1
     * <p>
     * 提示：
     * 1 <= envelopes.length <= 10^5
     * envelopes[i].length == 2
     * 1 <= wi, hi <= 10^5
     *
     * @param envelopes
     * @return
     */
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        int max = 0;
        // 二分查找
        for (int[] envelope : envelopes) {
            int temp = envelope[1];
            int left = 0, right = max;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] >= temp) {
                    right = mid;
                } else if (dp[mid] < temp) {
                    left = mid + 1;
                }
            }
            if (left == max) {
                max++;
            }
            dp[left] = temp;
        }
        // 动态规划查找，超时
        //for (int i = 0; i < envelopes.length; i++) {
        //    for (int j = 0; j < i; j++) {
        //        if (envelopes[i][1] > envelopes[j][1]) {
        //            dp[i] = Math.max(dp[i], dp[j] + 1);
        //        }
        //    }
        //    max = Math.max(max, dp[i]);
        //}
        return max;
    }

}
